package algocasts;

import java.util.ArrayList;
import java.util.List;

public class P138_LowestCommonAncestorOfABinaryTree {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }

    private boolean search(TreeNode root, TreeNode node, List<TreeNode> path) {
        if (root == null) return false;
        path.add(root);
        if (root == node) return true;
        boolean ret = search(root.left, node, path) || search(root.right, node, path);
        if (ret) return true;
        path.remove(path.size() - 1);
        return false;
    }

    // Time: O(n)  Space: O(n)
    public TreeNode lowestCommonAncestor_Path(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pPath = new ArrayList<>();
        List<TreeNode> qPath = new ArrayList<>();
        search(root, p, pPath);
        search(root, q, qPath);
        int i = 0, len = Math.min(pPath.size(), qPath.size());
        while (i < len && pPath.get(i) == qPath.get(i)) i++;
        return pPath.get(i - 1);
    }

    // Time: O(n)  Space: O(n)
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;
        else if (left != null) return left;
        else return right;
    }


}
